package _动态规划系列._高楼扔鸡蛋;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/30 20:03
 * <p>
 * 功能描述:  动态规划最关键的就是dp数组的定义
 */
public class Summary_0887 {

    /**
     * dp[k][m] = n
     * # 当前有 k 个鸡蛋，可以尝试扔 m 次鸡蛋
     * # 这个状态下，最坏情况下最多能确切测试一栋 n 层的楼
     * ​
     * # 比如说 dp[1][7] = 7 表示：
     * # 现在有 1 个鸡蛋，允许你扔 7 次;
     * # 这个状态下最多给你 7 层楼，
     * # 使得你可以确定楼层 F 使得鸡蛋恰好摔不碎
     * # （一层一层线性探查嘛）
     */
    public int superEggDrop(int K, int N) {
        int[][] dp = new int[K + 1][N + 1];
        //base case
        // dp[0][..] = 0 dp[..][0] = 0     Java默认初始化了

        int m = 0;
        while (dp[K][m] < N) {
            m++;     //穷举尝试次数m
            for (int k = 1; k < K + 1; k++) {  //穷举鸡蛋数

                dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
            }
        }

        return m;
    }
}
